package offerbook;

import utils.TreeNode;

import java.util.*;

/**
 * 之字形打印BT。换行输出换行
 * @date 2020/3/12 23:47
 */
public class Code61_LevelZigZagPrintTree {

    /**
     * 在{@link Code60_LevelPrintTree}基础上，增加判断当前行是奇数行还是偶数行。
     * 如果是奇数行，顺序打印。如果是偶数行，逆序打印。
     * 所以还要有额外的list来记录遍历的节点
     */
    public static void print(TreeNode root){
        if(root == null) return;
        int curPrint = 1;
        int nextPrint = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> pathList = new LinkedList<>();
        boolean odd = true;
        queue.add(root);
        while (!queue.isEmpty()){
            // 注意这里一定要先判断，再出队！！可以用第一层走一次
            if(curPrint == 0){
                curPrint = nextPrint;
                nextPrint = 0;
                doPrint(odd,pathList);
                odd = !odd;
            }
            root = queue.poll();
            curPrint--;
            if(root.left != null) {
                queue.offer(root.left);
                nextPrint++;
            }
            if(root.right != null) {
                queue.offer(root.right);
                nextPrint++;
            }
        }
        //注意处理最后一行
        doPrint(odd,pathList);
    }

    private static void doPrint(boolean odd, List<Integer> pathList) {
        if(odd){//奇数行，顺序打印
            for (Integer integer : pathList) {
                System.out.print(integer+" ");
            }
        }else {
            for (int size = pathList.size() -1; size >= 0; size--) {
                System.out.print(pathList.get(size)+" ");
            }
        }
        pathList.clear();
    }

    //牛客

    public static ArrayList<ArrayList<Integer>> print2(TreeNode root){
        if(root == null) return new ArrayList<>();
        int curPrint = 1;
        int nextPrint = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        //记录奇数行还是偶数行
        boolean odd = true;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        //同一层要打印的
        ArrayList<Integer> levelList = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            //如果当前遍历到第二层，那么处理第一层的结果。
            // 注意这里一定要先判断，再出队！！可以用第一层走一次
            if(curPrint == 0){
                curPrint = nextPrint;
                nextPrint = 0;
                doPrint(odd,levelList,res);
                odd = !odd;
            }
            root = queue.poll();
            curPrint -- ;
            levelList.add(root.val);
            if(root.left != null) {
                queue.offer(root.left);
                nextPrint++;
            }
            if(root.right != null) {
                queue.offer(root.right);
                nextPrint++;
            }
        }
        //退出循环，但是最后一层结果还没处理
        doPrint(odd,levelList,res);
        return res;
    }

    private static void doPrint(boolean odd, ArrayList<Integer> sameHeightList, ArrayList<ArrayList<Integer>> res) {
        if(odd){
            res.add(new ArrayList<>(sameHeightList));
        }else {
            Collections.reverse(sameHeightList);
            res.add(new ArrayList<>(sameHeightList));
        }
        sameHeightList.clear();
    }
}
